package Leetcode.DayTest;

import com.google.common.collect.Lists;

import java.util.*;

/**
 * @Author: kirito
 * @Date: 2024/5/27 11:46
 * @Description: 找出缺失的观测数据
 * 中等
 * 相关标签
 * 相关企业
 * 提示
 * 现有一份 n + m 次投掷单个 六面 骰子的观测数据，骰子的每个面从 1 到 6 编号。观测数据中缺失了 n 份，你手上只拿到剩余 m 次投掷的数据。幸好你有之前计算过的这 n + m 次投掷数据的 平均值 。
 *
 * 给你一个长度为 m 的整数数组 rolls ，其中 rolls[i] 是第 i 次观测的值。同时给你两个整数 mean 和 n 。
 *
 * 返回一个长度为 n 的数组，包含所有缺失的观测数据，且满足这 n + m 次投掷的 平均值 是 mean 。如果存在多组符合要求的答案，只需要返回其中任意一组即可。如果不存在答案，返回一个空数组。
 *
 * k 个数字的 平均值 为这些数字求和后再除以 k 。
 *
 * 注意 mean 是一个整数，所以 n + m 次投掷的总和需要被 n + m 整除。
 *
 *
 *
 * 示例 1：
 *
 * 输入：rolls = [3,2,4,3], mean = 4, n = 2
 * 输出：[6,6]
 * 解释：所有 n + m 次投掷的平均值是 (3 + 2 + 4 + 3 + 6 + 6) / 6 = 4 。
 * 示例 2：
 *
 * 输入：rolls = [1,5,6], mean = 3, n = 4
 * 输出：[2,3,2,2]
 * 解释：所有 n + m 次投掷的平均值是 (1 + 5 + 6 + 2 + 3 + 2 + 2) / 7 = 3 。
 * 示例 3：
 *
 * 输入：rolls = [1,2,3,4], mean = 6, n = 4
 * 输出：[]
 * 解释：无论丢失的 4 次数据是什么，平均值都不可能是 6 。
 * 示例 4：
 *
 * 输入：rolls = [1], mean = 3, n = 1
 * 输出：[5]
 * 解释：所有 n + m 次投掷的平均值是 (1 + 5) / 2 = 3 。
 */

public class missingRolls {
    public int[] missingRolls(int[] rolls, int mean, int n) {
        int sum = Arrays.stream(rolls).sum();
        int len = rolls.length;
        //剩余的骰子需要组成的点数之和
        int need = (len + n) * mean - sum;

        if (need > (n * 6) || need < n) {
            return new int[-1];
        }
        int quotient = need / n, remainder = need % n;
        int ans[] = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = quotient + (i < remainder ? 1 : 0);
        }
        return ans;
    }

    /**
     * 找出峰值
     * 简单
     * 相关标签
     * 相关企业
     * 提示
     * 给你一个下标从 0 开始的数组 mountain 。你的任务是找出数组 mountain 中的所有 峰值。
     *
     * 以数组形式返回给定数组中 峰值 的下标，顺序不限 。
     *
     * 注意：
     *
     * 峰值 是指一个严格大于其相邻元素的元素。
     * 数组的第一个和最后一个元素 不 是峰值。
     *
     *
     * 示例 1：
     *
     * 输入：mountain = [2,4,4]
     * 输出：[]
     * 解释：mountain[0] 和 mountain[2] 不可能是峰值，因为它们是数组的第一个和最后一个元素。
     * mountain[1] 也不可能是峰值，因为它不严格大于 mountain[2] 。
     * 因此，答案为 [] 。
     * 示例 2：
     *
     * 输入：mountain = [1,4,3,8,5]
     * 输出：[1,3]
     * 解释：mountain[0] 和 mountain[4] 不可能是峰值，因为它们是数组的第一个和最后一个元素。
     * mountain[2] 也不可能是峰值，因为它不严格大于 mountain[3] 和 mountain[1] 。
     * 但是 mountain[1] 和 mountain[3] 严格大于它们的相邻元素。
     * 因此，答案是 [1,3] 。
     *
     int* findPeaks(int* mountain, int mountainSize, int* returnSize) {
     int index = 0;
     // 分配内存空间用于存放峰值的数组，大小至少为mountainSize，加上1个额外的元素以存储可能的第三个峰值索引
     int* res = (int*)malloc((mountainSize + 1) * sizeof(int));
     for (int i = 1; i < mountainSize - 1; i++) {
     if (mountain[i - 1] < mountain[i] && mountain[i] > mountain[i + 1]) {
     res[index] = i;
     index++;
     }
     }
     // 设置返回的峰值数量
     *returnSize = index;
     return res;
     }
     * @param mountain
     * @return
     */
    public List<Integer> findPeaks(int[] mountain) {
        List<Integer> ans = new ArrayList<>();
        int len = mountain.length;
        if (len <= 2) {
            return ans;
        }
        for (int i = 1; i < len - 1; i++) {
            if (mountain[i] > mountain[i - 1] && mountain[i] > mountain[i + 1]) {
                ans.add(i);
            }
        }
        return ans;
    }

    /**
     * 2981. 找出出现至少三次的最长特殊子字符串 I
     * 中等
     * 相关标签
     * 相关企业
     * 提示
     * 给你一个仅由小写英文字母组成的字符串 s 。
     *
     * 如果一个字符串仅由单一字符组成，那么它被称为 特殊 字符串。例如，字符串 "abc" 不是特殊字符串，而字符串 "ddd"、"zz" 和 "f" 是特殊字符串。
     *
     * 返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度，如果不存在出现至少三次的特殊子字符串，则返回 -1 。
     *
     * 子字符串 是字符串中的一个连续 非空 字符序列。
     *
     *
     *
     * 示例 1：
     *
     * 输入：s = "aaaa"
     * 输出：2
     * 解释：出现三次的最长特殊子字符串是 "aa" ：子字符串 "aaaa"、"aaaa" 和 "aaaa"。
     * 可以证明最大长度是 2 。
     * 示例 2：
     *
     * 输入：s = "abcdef"
     * 输出：-1
     * 解释：不存在出现至少三次的特殊子字符串。因此返回 -1 。
     * 示例 3：
     *
     * 输入：s = "abcaba"
     * 输出：1
     * 解释：出现三次的最长特殊子字符串是 "a" ：子字符串 "abcaba"、"abcaba" 和 "abcaba"。
     * 可以证明最大长度是 1 。
     *
     *
     * 提示：
     *
     * 3 <= s.length <= 50
     * s 仅由小写英文字母组成。
     * @param
     * @return
     */
    public int maximumLength(String S) {
        char[] s = S.toCharArray();
        List<Integer>[] groups = new ArrayList[26];
        Arrays.setAll(groups, i -> new ArrayList<>());
        int cnt = 0;
        for (int i = 0; i < s.length; i++) {
            cnt++;
            if (i + 1 == s.length || s[i] != s[i + 1]) {
                groups[s[i] - 'a'].add(cnt); // 统计连续字符长度
                cnt = 0;
            }
        }

        int ans = 0;
        for (List<Integer> a : groups) {
            if (a.isEmpty()) continue;
            a.sort(Collections.reverseOrder());
            a.add(0);
            a.add(0); // 假设还有两个空串
            ans = Math.max(ans, Math.max(a.get(0) - 2, Math.max(Math.min(a.get(0) - 1, a.get(1)), a.get(2))));
        }

        return ans > 0 ? ans : -1;
    }

    /**
     * 2965. 找出缺失和重复的数字
     * 简单
     * 相关标签
     * 相关企业
     * 给你一个下标从 0 开始的二维整数矩阵 grid，大小为 n * n ，其中的值在 [1, n2] 范围内。除了 a 出现 两次，b 缺失 之外，每个整数都 恰好出现一次 。
     *
     * 任务是找出重复的数字a 和缺失的数字 b 。
     *
     * 返回一个下标从 0 开始、长度为 2 的整数数组 ans ，其中 ans[0] 等于 a ，ans[1] 等于 b 。
     *
     *
     *
     * 示例 1：
     *
     * 输入：grid = [[1,3],[2,2]]
     * 输出：[2,4]
     * 解释：数字 2 重复，数字 4 缺失，所以答案是 [2,4] 。
     * 示例 2：
     *
     * 输入：grid = [[9,1,7],[8,9,2],[3,4,6]]
     * 输出：[9,5]
     * 解释：数字 9 重复，数字 5 缺失，所以答案是 [9,5] 。
     *
     *
     * 提示：
     *
     * 2 <= n == grid.length == grid[i].length <= 50
     * 1 <= grid[i][j] <= n * n
     * 对于所有满足1 <= x <= n * n 的 x ，恰好存在一个 x 与矩阵中的任何成员都不相等。
     * 对于所有满足1 <= x <= n * n 的 x ，恰好存在一个 x 与矩阵中的两个成员相等。
     * 除上述的两个之外，对于所有满足1 <= x <= n * n 的 x ，都恰好存在一对 i, j 满足 0 <= i, j <= n - 1 且 grid[i][j] == x 。
     * @param grid
     * @return
     */
    public int[] findMissingAndRepeatedValues(int[][] grid) {
        int n = grid.length;
        int[] count = new int[n * n + 1];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                count[grid[i][j]]++;
            }
        }

        int[] res = new int[2];
        for (int i = 1; i <= n * n; i++) {
            if (count[i] == 2) {
                res[0] = i;
            }
            if (count[i] == 0) {
                res[1] = i;
            }
        }
        return res;
    }

    /**
     *  分糖果
     * 简单
     * 相关标签
     * 相关企业
     * 提示
     * Alice 有 n 枚糖，其中第 i 枚糖的类型为 candyType[i] 。Alice 注意到她的体重正在增长，所以前去拜访了一位医生。
     *
     * 医生建议 Alice 要少摄入糖分，只吃掉她所有糖的 n / 2 即可（n 是一个偶数）。Alice 非常喜欢这些糖，她想要在遵循医生建议的情况下，尽可能吃到最多不同种类的糖。
     *
     * 给你一个长度为 n 的整数数组 candyType ，返回： Alice 在仅吃掉 n / 2 枚糖的情况下，可以吃到糖的 最多 种类数。
     *
     *
     *
     * 示例 1：
     *
     * 输入：candyType = [1,1,2,2,3,3]
     * 输出：3
     * 解释：Alice 只能吃 6 / 2 = 3 枚糖，由于只有 3 种糖，她可以每种吃一枚。
     * 示例 2：
     *
     * 输入：candyType = [1,1,2,3]
     * 输出：2
     * 解释：Alice 只能吃 4 / 2 = 2 枚糖，不管她选择吃的种类是 [1,2]、[1,3] 还是 [2,3]，她只能吃到两种不同类的糖。
     * 示例 3：
     *
     * 输入：candyType = [6,6,6,6]
     * 输出：1
     * 解释：Alice 只能吃 4 / 2 = 2 枚糖，尽管她能吃 2 枚，但只能吃到 1 种糖。
     *
     *
     * 提示：
     *
     * n == candyType.length
     * 2 <= n <= 104
     * n 是一个偶数
     * -105 <= candyType[i] <= 105
     * @param candyType
     * @return
     */
    public int distributeCandies(int[] candyType) {
        int ans = 0;
        Set<Integer> set = new HashSet<>();
        int len = candyType.length;
        int max = len / 2;
        for (int i = 0; i < len; i++) {
            set.add(candyType[i]);
        }
        int size = set.size();
        ans = Math.min(size, max);
        return ans;
    }

}
